/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: ws
 * Date: 2023-06-22
 * Time: 23:39
 */
import java.util.*;
//https://www.nowcoder.com/questionTerminal/2237b401eb9347d282310fc1c3adb134?answerType=1&f=discussion

//背包思路

//public class Solution3 {
//    public int maxValue (int[][] grid) {
//        int row = grid.length;
//        int col = grid[0].length;
//        for (int i = 1; i < row; i++) {
//            grid[i][0] += grid[i - 1][0];
//        }
//        for (int i = 1; i < col; i++) {
//            grid[0][i] += grid[0][i - 1];
//        }
//        for (int i = 1; i < row; i++) {
//            for (int j = 1; j < col; j++) {
//                grid[i][j] += Math.max(grid[i - 1][j], grid[i][j - 1]);
//            }
//        }
//        return grid[row - 1][col - 1];
//    }
//}

public class Solution3 {
    public static int maxValue(int[][] grid) {
        int row = grid.length;
        int col = grid[0].length;
        int[][] dp = new int[row][col];
        //row和col记得-1，让其合法
        return recursion(grid, row - 1, col - 1, dp);
    }

    //递归法
    public static int recursion(int[][] grid, int x, int y, int[][] dp) {
        //递归到左上角
        if (x == 0 && y == 0) {
            dp[x][y] = grid[x][y];
            return grid[x][y];
        }
        //递归到第一列
        if (y == 0) {
            //加上该位置本身的，以及该位置的上一行（因为已经到了左边界，只有一条路）
            dp[x][0] = grid[x][0] + recursion(grid, x - 1, y, dp);
        }
        //递归到第一行
        if (x == 0) {
            //同理
            dp[0][y] = grid[0][y] + recursion(grid, x, y - 1, dp);
        }
        if (dp[x][y] == 0) {
            //无论怎样必定会走到最后一个格子
            dp[x][y] = grid[x][y] + Math.max(recursion(grid, x - 1, y, dp), recursion(grid, x, y - 1, dp));
        }
        return dp[x][y];
    }
}